class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        # 前期准备
        cheesBoard = [0 for _ in range(n)]  # 棋盘（位运算）（0~n-1）
        lineFlag = [0]    # 棋子列影响标记
        res = []

        def dfs(level: int):
            # 成功找到
            if level == n:
                res.append(cheesBoard.copy())
                return

            # 搜索下一状态
            for i in range(n):
                # 剪枝
                if lineFlag[0] & (1 << i):
                    continue
                flag = False
                for j in range(1, n):
                    if level - j < 0 or i - j < 0:
                        break
                    if cheesBoard[level - j] & (1 << (i - j)):
                        flag = True
                        break
                for j in range(1, n):
                    if level - j < 0 or i + j >= n:
                        break
                    if cheesBoard[level - j] & (1 << (i + j)):
                        flag = True
                        break
                if flag:
                    continue

                # 下一层
                cheesBoard[level] |= (1 << i)
                lineFlag[0] |= (1 << i)
                dfs(level + 1)

                # 回溯
                cheesBoard[level] ^= (1 << i)
                lineFlag[0] ^= (1 << i)
            return

        dfs(0)

        # 答案转换
        tempBoard = [['.' for __ in range(n)] for _ in range(n)]
        tempRes = ["" for _ in range(n)]
        for i in range(len(res)):
            for j in range(len(res[i])):
                for k in range(n):
                    if res[i][j] & (1 << k):
                        tempBoard[j][k] = 'Q'
                    else:
                        tempBoard[j][k] = '.'
            for j in range(len(tempBoard)):
                tempRes[j] = "".join(tempBoard[j])
            res[i] = tempRes.copy()

        return res
